package map;


import java.util.*;

/**
 * https://leetcode.cn/problems/top-k-frequent-elements/?favorite=2cktkvj
 *
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 */
public class _347_前k个高频元素 {

    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }


        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });

        Set<Integer> keySet = map.keySet();

        for (Integer key : keySet) {
            if (queue.size() < k) {
                queue.offer(key);
            } else {
                if (map.get(key) > map.get(queue.peek())) {
                    queue.remove();
                    queue.offer(key);
                }

            }
        }


        int i = 0;

        while (!queue.isEmpty()) {
            result[i] = queue.poll();
            i++;
        }
        return result;
    }
}
